package com.ly.algorithm.leetcode.dp;

import java.util.Arrays;

/**
 * @Classname Problem392
 * @Description
 *
 * 示例 1：
 *
 * 输入：s = "abc", t = "ahbgdc"
 * 输出：true
 * 示例 2：
 *
 * 输入：s = "axc", t = "ahbgdc"
 * 输出：false
 *
 *
 * @Date 2020/12/25 10:28
 * @Author 冷心影翼
 */
public class Problem392 {

	public static void main(String[] args) {
		Solution392 solution392 = new Solution392();
		System.out.println(solution392.isSubsequence("ace", "abcde"));
	}

}



class Solution392 {
	public boolean isSubsequence(String s, String t) {
		int n1 = s.length();
		int n2 = t.length();
		boolean[][] dp = new boolean[n1+1][n2+1];
		Arrays.fill(dp[0],true);
		for (int i = 1; i <= n1; i++) {
			for (int j = 1; j <= n2; j++) {
				if(s.charAt(i-1) != t.charAt(j-1)) {
					dp[i][j] =  dp[i][j-1];
				}else {
					dp[i][j] = dp[i-1][j-1] ;
				}
			}
		}
		return dp[n1][n2];
	}
}